#!/usr/bin/env python
# encoding: utf-8
'''
@author: Excelsiorly
@license: (C) Copyright 2022, All Rights Reserved.
@contact: excelsiorly@qq.com
@file: 958. 二叉树的完全性检验.py
@time: 2022/3/6 20:55
@desc: https://leetcode-cn.com/problems/check-completeness-of-a-binary-tree/
> 给定一个二叉树的root，确定它是否是一个完全二叉树。
在一个完全二叉树中，除了最后一个关卡外，所有关卡都是完全被填满的，并且最后一个关卡中的所有节点都是尽可能靠左的。它可以包含1到2h节点之间的最后一级 h 。

1. bfs, Ot(n)
2. 在完全二叉树中，用 1 表示根节点编号，则对于任意一个节点 x，它的左孩子为 2*x，右孩子为 2*x + 1 。
    那么我们可以发现，一颗二叉树是完全二叉树当且仅当节点编号依次为 1, 2, 3, ...n 且没有间隙。
    换句话说，可以将其表示为一个值为1~n的连续数组。而在一个值从1开始的连续数组中，数组中最大元素值等于数组大小。
    在根节点编号值为1的完全二叉树则是，节点编号最大值等于节点个数。
    因此，我们可以对一颗二叉树进行dfs搜索，如果搜索出的节点编号序列值恰好可以组成一个升序的数组并且编号序列是一个从1开始的无间隔的连续数组，
    则该二叉树为完全二叉树。

'''
# Definition for a binary tree node.
class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right

class Solution:
    def isCompleteTree(self, root: TreeNode) -> bool:
        def dfs(root, k):
            # 遍历到了叶子节点
            if not root: return True
            # 更新结点数量
            self.n += 1
            # 记录最大的节点值
            self.p = max(self.p, k)
            return dfs(root.left, 2*k) and dfs(root.right, 2*k+1)
        # 记录节点数， 记录当前遍历到的最大节点编号
        self.n, self.p = 0, 0
        dfs(root, 1)
        return self.n==self.p
